#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

class Solution
{
public:
	int nthUglyNumber(int n)
	{
		if (n <= 1) return 1;
		vector<int> nums(n, 0);
		nums[0] = 1;
		int f2 = 0, f3 = 0, f5 = 0;
		for (int i = 1; i < n; i++)
		{
			int m2 = nums[f2] * 2;
			int m3 = nums[f3] * 3;
			int m5 = nums[f5] * 5;
			if (m2 <= m3 && m2 <= m5)
			{
				nums[i] = m2;
				f2++;
			}
			else if (m3 <= m2 && m3 <= m5)
			{
				nums[i] = m3;
				f3++;
			}
			else
			{
				nums[i] = m5;
				f5++;
			}
			if (nums[i] == nums[i - 1]) i--;
		}
		return nums[n - 1];
	}
};

int main()
{
	int constexpr;
	
}
